# 冒泡排序
def bubbleSort(alist):
    for i in range(1,len(alist)):
        # exchange = False
        for j in range(len(alist)-i):
           if alist[j]>alist[j+1]:
               exchange=True
               temp = alist[j]
               alist[j]=alist[j+1]
               alist[j+1] =temp
        # if not exchange:
        #     break
        print(alist)
    return alist
# print(bubbleSort([1, 99, 32, 8, 17, 19, 42, 13]))

# 改进的冒泡排序
# 当一趟比较没有交换时, 就表示列表已经有序
def bubbleSortv(alist):
    for i in range(1,len(alist)):
        exchange = False
        for j in range(len(alist)-i):
           if alist[j]>alist[j+1]:
               exchange=True
               alist[j+1], alist[j] = alist[j], alist[j+1]
        if not exchange:
            break
        print(alist)
    return alist
# print(bubbleSortv([1, 99, 32, 8, 17, 19, 42, 13]))


# 选择排序
# 在每趟比较中,记录最大值, 最后再交换
# 这样比冒泡排序减少交换的次数
def selectSort(alist):   
    for i in range(1,len(alist)):
        pos =0
        for j in range(len(alist)-i+1):
            
            if alist[j]>alist[pos]:
                pos = j
        if pos != j:
            alist[pos], alist[j] = alist[j], alist[pos]
        print(alist)
    return alist

# 插入排序算法:
# 假设部分有序, 待插入元素从后往前查找插入位置
# 最终得到一个升序的数据队列

def insertSort(alist):
    for index in range(1, len(alist)):
        currentValue = alist[index]
        position = index

        while position>0 and alist[position-1]>currentValue:
            alist[position]=alist[position-1]
            position = position-1
        alist[position]=currentValue
    return alist
# print(insertSort([1, 99, 32, 8, 17, 19, 42, 13]))


# shell排序: 是对插入排序的改进
# 首先以一定的间隔将数据序列分组, 对每个分组进行插入排序, 最后在对整个表进行排序
def shellSort(alist):
    sublistCount = len(alist)//2
    while sublistCount>0:
        for startpos in range(sublistCount):
            gapInsertSort(alist, startpos, sublistCount)

        print("After increments of size", sublistCount, "This list is ", alist)
        sublistCount=sublistCount//2
    return alist
def gapInsertSort(alist, start, gap):
    for i in range(start+gap, len(alist), gap):
        currentValue = alist[i]
        pos=i
        while pos>=gap and alist[pos-gap]>currentValue:
            alist[pos]=alist[pos-gap]
            pos = pos - gap
        alist[pos]=currentValue



# 归并排序:
#     使用了递归算法, 将列表一直切分直到只有一个元素为止;
#     重要的是再合并
def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf =alist[mid:]

        # 调用递归
        mergeSort(lefthalf)
        mergeSort(righthalf)

        # 合并的过程
        i=j=k=0
        while i<len(lefthalf) and j<len(righthalf):
            # 从两个表分别取出一个数, 然后比较大小, 总是添加小的
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i += 1
            else:
                alist[k]=righthalf[j]
                j+=1
            k+=1
        
        # 将左半部分剩余添加过来
        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i+=1
            k+=1
        
        # 将右半部分剩余添加过来
        while j< len(righthalf):
            alist[k]=righthalf[j]
            j+=1
            k+=1
    return alist


# print(mergeSort([1, 99, 32, 8, 17, 19, 42, 13]))


# 快速排序
#     寻求一个"中值", 然后切分数据为两部分, 然后递归

def quickSort(alist):
    quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):
    if first < last:
        splitPoint = partition(alist, first, last)

        quickSortHelper(alist, first, splitPoint-1)
        quickSortHelper(alist, splitPoint+1, last)

def partition(alist, first, last):
    # 取中值: 这里粗略以第一个数为中值
    pivotValue = alist[first]

    # 设定左右标的初始值
    leftMark = first +1
    rightMark = last

    done = False
    while not done:
        # 左标右移
        while leftMark<=rightMark and alist[leftMark]<=pivotValue:
            leftMark += 1
        
        # 右标左移
        while alist[rightMark]>=pivotValue and rightMark>=leftMark:
            rightMark -= 1

        # 左右标交错, 就停止移动
        if rightMark<leftMark:
            done = True
        else:
            # 交换左右标的值
            alist[leftMark], alist[rightMark]=alist[rightMark], alist[leftMark]

    # 中值就位
    alist[first], alist[rightMark]=alist[rightMark], alist[first]

    return rightMark

alist =[54,26,93,17,7,77,31,44, 55,20]
quickSort(alist)
print(alist)